/**
 * @description 二分查找
 * @author 李子一
 */

// 循环
/**
 * 二分查找(循环)
 * @param arr arr
 * @param target target
 */
export function binarySearch1(arr: number[], target: number): number {
	const length = arr.length
	if (length === 0) {
		return -1
	}

	let startIndex = 0
	let endIndex = length - 1
	while (startIndex <= endIndex) {
		const midIndex = Math.floor((startIndex + endIndex) / 2)
		const midValue = arr[midIndex]
		if (target < midValue) {
			// 目标值较小,继续在左侧查找
			endIndex = midIndex - 1
		} else if (target > midValue) {
			// 目标值较小,继续在右侧查找
			startIndex = midIndex + 1
		} else {
			return midIndex
		}
	}
	return -1
}

// 递归
export function binarySearch2(arr: number[], target: number): number {
	const length = arr.length
	if (length === 0) {
		return -1
	}

	function util(
		arr: number[],
		target: number,
		startIndex = 0,
		endIndex = arr.length - 1
	): number {
		if (startIndex > endIndex) {
			return -1
		}

		const midIndex = Math.floor((startIndex + endIndex) / 2)
		const midValue = arr[midIndex]
		if (target < midValue) {
			// 目标值较小,继续在左侧查找
			endIndex = midIndex - 1
			return util(arr, target, startIndex, endIndex)
		} else if (target > midValue) {
			// 目标值较小,继续在右侧查找
			startIndex = midIndex + 1
			return util(arr, target, startIndex, endIndex)
		} else {
			return midIndex
		}
	}

	return util(arr, target)
}
const arr1 = [1, 2, 3, 4, 5],
	target = 1
console.log(binarySearch1(arr1, target))
